package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-06-27 17:59
 */
public class 题库_0131_分割回文串 {

  static
  class Solution {
    public List<List<String>> partition(String s) {
      List<List<String>> answer = new ArrayList<>();
      if (s == null || s.length() == 0) {
        return answer;
      }
      boolean[][] mark = new boolean[s.length()][s.length()];
      for (int i = 0; i < s.length(); ++i) {
        for (int j = i; j < s.length(); ++j) {
          if (isPalindrome(s, i, j, mark)) {
            mark[i][j] = true;
          }
        }
      }
      return answer;
    }

    private boolean isPalindrome(String s, int left, int right, boolean[][] mark) {
      while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
          return false;
        }
        if (mark[left][right]) {
          return true;
        }
        ++left;
        --right;
      }
      return true;
    }
  }

}
